package com.hanxiaozhang.no3algorithm.dynamicprogramming;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈0-1背包问题〉
 *
 * @author hanxinghua
 * @create 2023/10/27
 * @since 1.0.0
 */
public class No1ZeroOnePack {


    public static void main(String[] args) {

        // 物品价值数组 - 索引0位置不用
        int[] v = new int[]{0, 2, 4, 5, 6};
        // 物品重量数组 - 索引0位置不用
        int[] w = new int[]{0, 1, 2, 3, 4};

        // 物品数量
        int num = 4;
        // 背包容量
        int cap = 5;
        int max = pack1(v, w, num, cap);
        System.out.println("装入背包的最大价值是：" + max);
    }

    /**
     * 0-1 背包问题。
     *
     * @param v   物品价值数组 - 索引0位置不用
     * @param w   物品重量数组 - 索引0位置不用
     * @param num 物品数量
     * @param cap 背包容量
     * @return
     */
    private static int pack1(int[] v, int[] w, int num, int cap) {

        // 创建子问题表格
        int[][] f = new int[num + 1][cap + 1];
        // 最大容量
        int max = 0;

        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= cap; j++) {
                int not = 0, yes = 0;

                // 不选择第i个物品
                not = f[i - 1][j];
                // 选择第i个物品 前提条件：背包容量j 大于等于 第i个物品的重量才能选。
                if (j == w[i]) {
                    yes = v[i];
                }
                if (j > w[i]) {
                    yes = v[i] + f[i - 1][j - w[i]];
                }
                // "不选第i个物品" 和 "选择第i个物品"两者的最大值
                f[i][j] = Math.max(not, yes);
                if (f[i][j] > max) {
                    max = f[i][j];
                }
            }
        }
        print(f);
        return max;
    }

    public static void print(int[][] array) {
        System.out.println("0-1背包子问题数组：");
        for (int[] row : array) {
            for (int i : row) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

}
